package com.jxb.seven;

/**
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 *
 * dp数组：
 *  leftDP用以记录i左边的最大高度，rightDP用来记录右边的最大高度
 *  leftDP[i] = max(leftDP[i-1],height[i])
 *  rightDP[i] = max(rightDP[i+1],height[i])
 *  填充完leftDP和rightDP后，每个元素i能获得的水量自然就是：min(leftDP[i] ,rightDP[i]) - height[i]
 */
public class TrappingRainWater_42 {

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        trap(height);
    }


    /*动态规划实现*/
    public static int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        //正向遍历，填充leftDP数组
        int[] leftDp = new int[n];
        leftDp[0] = height[0];
        for (int i = 1;i<n;++i) {
            leftDp[i] = Math.max(leftDp[i-1],height[i]);
        }
        //反向遍历，填充rightDP数组
        int[] rightDp = new int[n];
        rightDp[n-1] = height[n-1];
        for (int i = n - 2;i>=0;--i) {
            rightDp[i] = Math.max(rightDp[i+1],height[i]);
        }
        //遍历每个下标的位置即可接到雨水的总量
        int result = 0;
        //i=1,leftDp[0]=0,rightDp[0]=
        //result = 0 +
        for (int i = 0;i<n;++i) {
            result += Math.min(leftDp[i], rightDp[i]) - height[i];
        }
        return result;

    }



}
